package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.StackProblem;
import cn.pugle.oj.catalog.TwoProblem;

import java.util.LinkedList;

/**
 * TODO 双指针法
 *
 * @author tzp
 * @since 2020/9/24
 */
public class LC42_1 implements StackProblem, TwoProblem {
    public int trap(int[] heights) {
        if (heights == null || heights.length <= 2) return 0;
        int left = 0, right = heights.length - 1;
        int lMax = 0, rMax = heights.length - 1;
        int sum = 0;
        while (left < right) {
            if (heights[left] <= heights[right]) {
                left++;
                if (heights[left] >= heights[lMax]) {
                    lMax = left;
                } else {
                    sum += Math.min(heights[lMax], heights[rMax]) - heights[left];
                }
            } else {
                right--;
                if (heights[right] >= heights[rMax]) {
                    rMax = right;
                } else {
                    sum += Math.min(heights[lMax], heights[rMax]) - heights[right];
                }
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        System.out.println(new LC42_1().trap(new int[]{4, 2, 3}));
        System.out.println(new LC42_1().trap(new int[]{1, 2, 1, 3, 2, 1, 2, 4, 3, 2, 3, 2}));
        System.out.println(new LC42_1().trap(new int[]{4, 2, 0, 3, 2, 5}));//9
    }
}
